#include "BTreeIndex.h"
#include <cstring>
#include <cstdlib>
#include <assert.h>
#include <cstdio>
#include "Objects.h"




BtreeIndex::BtreeIndex()
{
    //
}


BtreeIndex::~BtreeIndex()
{
    //
}

void BtreeIndex::Init()
{
    root = alloc_bucket();
    root->lock.Init();
    root->layer = 1;
    root->father = root->prev_leaf = root->next_leaf = NULL;
    root->element_num = 0;
    leaf_head = root;
    leaf_tail = root;

    rwlock.Init();

    bucket_num = 0;

    RebalanceOp = 0;
    element_num = 0;
    mem_used = 0;
}

void BtreeIndex::Destroy()
{
    //Lock is not necessary. Should guarantee thread-safe outside the function.
    dfs_destroy(root);
    free_bucket(root);
    rwlock.Destroy();
}

int item_compare(Item *a, Item *b)
{
    int len = MIN(a->KeyLength(), b->KeyLength());
    int res = memcmp(a->data, b->data, len);
    if (res != 0) return res;
    else return (a->KeyLength() - b->KeyLength());
}


Item* BtreeIndex::Set(Item *item, int set_mode)
{
    BtreeBucket *trav_tree = root;
    Item *res = item;
    int trav_path[10];
    int final_pos;
    int write_lock = 0;

RELOOP:
    if (write_lock) rwlock.WLock(); else rwlock.RLock();

    trav_tree = root;
    
    while(trav_tree->layer > 1)
    {
        int pos = trav_tree->FindPosNode(item,CompareFunc);
        //Remember the traverse path
        trav_path[trav_tree->layer] = pos;
        trav_tree = reinterpret_cast<BtreeBucket*>(trav_tree->ptrs[pos]);
    }

    trav_tree->lock.Lock();
    final_pos = trav_tree->FindPosLeaf(item, CompareFunc);

    //Check if the item already exists.
    if (final_pos >= 0) 
    {
        if (set_mode == REPLACE)
        {
            Item *tmp_item;
            u64 swap_real_pos, swap_cache_idx;
            u32 swap_len;

            if (final_pos == 0 && !write_lock)
            {
                trav_tree->lock.UnLock();
                rwlock.UnLock();
                write_lock = 1;
                goto RELOOP;
            }

            if (final_pos == 0)
            {
                //replace if it is an anchor
                BtreeBucket *tran_tree_2 = root;
                while(tran_tree_2->layer > 1)
                {
                    if (trav_path[tran_tree_2->layer] > 0 
                        && tran_tree_2->ptrs[trav_path[tran_tree_2->layer]-1] == trav_tree->ptrs[final_pos])
                    {
                        //found the anchor with this item, fix it
                        tran_tree_2->ptrs[trav_path[tran_tree_2->layer]-1] = item;
                        break;
                    }
                    tran_tree_2 = reinterpret_cast<BtreeBucket*>(tran_tree_2->ptrs[trav_path[tran_tree_2->layer]]);
                }
            }
            tmp_item = reinterpret_cast<Item*>(trav_tree->ptrs[final_pos]);
            trav_tree->ptrs[final_pos] = item;
            tmp_item->GetRef();
            trav_tree->lock.UnLock();
            rwlock.UnLock();
            return tmp_item;
        }
        trav_tree->lock.UnLock();
        rwlock.UnLock();
        return NULL;
    }
    else if (set_mode == REPLACE_ONLY_EXIST)
    {
        trav_tree->lock.UnLock();
        rwlock.UnLock();
        return NULL;
    }

    if (trav_tree->element_num + 1 == 2*BTREEDEGREE + 1 && !write_lock)
    {
        trav_tree->lock.UnLock();
        rwlock.UnLock();
        write_lock = 1;
        goto RELOOP;
    }

    //Make 1 slot and put in the item
    final_pos = -final_pos-1;
    if (final_pos == 0 && !write_lock)
    {
        trav_tree->lock.UnLock();
        rwlock.UnLock();
        write_lock = 1;
        goto RELOOP;
    }

    trav_tree->MakeSpaceInBucket(final_pos, 1);
    trav_tree->ptrs[final_pos] = item;
    element_num++;

    if (final_pos == 0)
    {
        BtreeBucket *tran_tree_2 = root;
        while(tran_tree_2->layer > 1)
        {
            if (trav_path[tran_tree_2->layer] > 0 
                && tran_tree_2->ptrs[trav_path[tran_tree_2->layer]-1] == trav_tree->ptrs[1])
            {
                //found the anchor with this item, fix it
                tran_tree_2->ptrs[trav_path[tran_tree_2->layer]-1] = item;
                break;
            }
            tran_tree_2 = reinterpret_cast<BtreeBucket*>(tran_tree_2->ptrs[trav_path[tran_tree_2->layer]]);
        }
    }

    //Check if the bucket is full
    if (trav_tree->element_num < 2*BTREEDEGREE+1)
    {
        res->GetRef();
        trav_tree->lock.UnLock();
        rwlock.UnLock();
        return res;
    }

    RebalanceOp++;
//===============================overflow==============================
    //Left neighbor exists and not so full, move some elements at left side to the neighbor
    if (trav_tree->prev_leaf != NULL
        && trav_tree->prev_leaf->father == trav_tree->father 
        && trav_tree->prev_leaf->element_num < BTREEDEGREE * 1.6)
    {
        //magic number 'BTREEDEGREE * 0.2' to make balance
        trav_tree->MoveLeftToLeafBucket((int)(BTREEDEGREE*0.2), trav_tree->prev_leaf);
        //Update the anchor of this bucket with the new left-most key element
        trav_tree->father->ptrs[trav_path[2]-1] = trav_tree->ptrs[0];
    }
    //So does the right neighbor
    else if (trav_tree->next_leaf != NULL
        && trav_tree->next_leaf->father == trav_tree->father
        && trav_tree->next_leaf->element_num < BTREEDEGREE * 1.6)
    {
        trav_tree->MoveRightToLeafBucket((int)(BTREEDEGREE*0.2), trav_tree->next_leaf);
        trav_tree->father->ptrs[trav_path[2]+1] = trav_tree->next_leaf->ptrs[0];
    }
    //Can't move out, split an new neighbor on right
    else
    {
        BtreeBucket *new_leaf = alloc_bucket();
        new_leaf->lock.Init();
        if (trav_tree->next_leaf != NULL)
            trav_tree->next_leaf->prev_leaf = new_leaf;
        new_leaf->next_leaf = trav_tree->next_leaf;
        new_leaf->prev_leaf = trav_tree;
        trav_tree->next_leaf = new_leaf;
        new_leaf->father = trav_tree->father;
        //layer 1 means the leafs, the top layer bucket is the root
        new_leaf->layer = 1;
        new_leaf->element_num = 0;
        if (leaf_tail == trav_tree)
            leaf_tail = new_leaf;

        //move half of the elements
        trav_tree->MoveRightToLeafBucket(BTREEDEGREE, new_leaf);
        //insert a node to parent node bucket, the new leaf's left-most element as key, and new leaf as ptr.
        insert_node(trav_tree->father, reinterpret_cast<Item*>(new_leaf->ptrs[0]), new_leaf, &trav_path[0]);
    }
//==============================overflow===============================
    res->GetRef();
    trav_tree->lock.UnLock();
    rwlock.UnLock();
    return res;
}


Item* BtreeIndex::Get(Item *item)
{
    BtreeBucket *trav_tree;
    int final_pos;
    Item *res = NULL; 

    rwlock.RLock();
    trav_tree = root;
    while(trav_tree->layer > 1)
        trav_tree = reinterpret_cast<BtreeBucket*>(trav_tree->ptrs[trav_tree->FindPosNode(item,CompareFunc)]);

    trav_tree->lock.Lock();
    final_pos = trav_tree->FindPosLeaf(item, CompareFunc);
    if (final_pos >= 0 )
    {
        res = reinterpret_cast<Item*>(trav_tree->ptrs[final_pos]);
        res->GetRef();
    }

    trav_tree->lock.UnLock();
    rwlock.UnLock();
    return res;
}

Item* BtreeIndex::Delete(Item *item)
{
    BtreeBucket *trav_tree;
    Item *tmp_item;
    Item *res = NULL;
    int tra_path[10];
    int final_pos;
    int write_lock = 0;

RELOOP:
    if (write_lock) rwlock.WLock(); else rwlock.RLock();

    trav_tree = root;

    while(trav_tree->layer > 1)
    {
        int pos = trav_tree->FindPosNode(item,CompareFunc);
        tra_path[trav_tree->layer] = pos;
        trav_tree = reinterpret_cast<BtreeBucket*>(trav_tree->ptrs[pos]);
    }

    trav_tree->lock.Lock();
    final_pos = trav_tree->FindPosLeaf(item, CompareFunc);

    //Check if the item exists.
    if (final_pos < 0) 
    {
        trav_tree->lock.UnLock();
        rwlock.UnLock();
        return res;
    }

    if (final_pos == 0 && !write_lock)
    {
        trav_tree->lock.UnLock();
        rwlock.UnLock();
        write_lock = 1;
        goto RELOOP;
    }

    if (trav_tree->element_num - 1 <= BTREEDEGREE * 0.7 && !write_lock)
    {
        trav_tree->lock.UnLock();
        rwlock.UnLock();
        write_lock = 1;
        goto RELOOP;
    }

    res = reinterpret_cast<Item*>(trav_tree->ptrs[final_pos]);
    res->GetRef();
    trav_tree->DeleteInBucket(final_pos, 1);
    element_num--;

    //if deleted the left corner element, it must be an anchor in one bucket, fix it with the new one
    if (final_pos == 0)
    {
        BtreeBucket *tran_tree_2 = root;
        while(tran_tree_2->layer > 1)
        {
            if (tra_path[tran_tree_2->layer] > 0 
                && tran_tree_2->ptrs[tra_path[tran_tree_2->layer]-1] == res)
                //it doesn't matter that tmp_item has been myfreed
            {
                //found the anchor with this item, fix it
                tran_tree_2->ptrs[tra_path[tran_tree_2->layer]-1] = trav_tree->ptrs[0];
                break;
            }
            tran_tree_2 = reinterpret_cast<BtreeBucket*>(tran_tree_2->ptrs[tra_path[tran_tree_2->layer]]);
        }
    }

    //check if it is too empty
    if (trav_tree->element_num > BTREEDEGREE * 0.7)
    {
        trav_tree->lock.UnLock();
        rwlock.UnLock();
        return res;
    }

    RebalanceOp++;
    //===============================underflow==============================
    //Left neighbor have much more elements, move them to this poor bucket
    if (trav_tree->prev_leaf != NULL
        && trav_tree->prev_leaf->father == trav_tree->father 
        && trav_tree->prev_leaf->element_num > BTREEDEGREE * 1.3)
    {
        //BTREEDEGREE*0.2 to make balance 
        trav_tree->prev_leaf->MoveRightToLeafBucket(BTREEDEGREE*0.3, trav_tree);
        //fix the anchor
        trav_tree->father->ptrs[tra_path[2]-1] = trav_tree->ptrs[0];
    }
    //Opposite to the left
    else if (trav_tree->next_leaf != NULL
        && trav_tree->next_leaf->father == trav_tree->father
        && trav_tree->next_leaf->element_num > BTREEDEGREE * 1.3)
    {
        trav_tree->next_leaf->MoveLeftToLeafBucket(BTREEDEGREE*0.3, trav_tree);
        trav_tree->father->ptrs[tra_path[2]+1] = trav_tree->next_leaf->ptrs[0];
    }
    //Can be merged with left neighbor
    else if (trav_tree->next_leaf != NULL
        && trav_tree->next_leaf->father == trav_tree->father
        && trav_tree->next_leaf->element_num + trav_tree->element_num < BTREEDEGREE * 1.8)
    {
        BtreeBucket *next_leaf = trav_tree->next_leaf;
        next_leaf->MoveLeftToLeafBucket(next_leaf->element_num, trav_tree);
        if (next_leaf->next_leaf != NULL)
            next_leaf->next_leaf->prev_leaf = trav_tree;
        trav_tree->next_leaf = next_leaf->next_leaf;
        next_leaf->lock.Destroy();
        if (leaf_tail == next_leaf)
            leaf_tail = trav_tree;
        free_bucket(next_leaf);

        //delete the current's anchor and link from the parent node
        delete_node(trav_tree->father, tra_path[2]+1, 2, &tra_path[0]);
    }
    //Can be merged with right neighbor
    else if (trav_tree->prev_leaf != NULL
        && trav_tree->prev_leaf->father == trav_tree->father
        && trav_tree->prev_leaf->element_num + trav_tree->element_num < BTREEDEGREE * 1.8)
    {
        BtreeBucket *prev_leaf = trav_tree->prev_leaf;
        prev_leaf->MoveRightToLeafBucket(prev_leaf->element_num, trav_tree);
        if (prev_leaf->prev_leaf != NULL)
            prev_leaf->prev_leaf->next_leaf = trav_tree;
        trav_tree->prev_leaf = prev_leaf->prev_leaf;
        prev_leaf->lock.Destroy();
        if (leaf_head == prev_leaf)
            leaf_head = trav_tree;
        free_bucket(prev_leaf);

        delete_node(trav_tree->father, tra_path[2]-2, 2, &tra_path[0]);
    }
    //==============================underflow===============================
    trav_tree->lock.UnLock();
    rwlock.UnLock();
    return res;
}


void BtreeIndex::insert_node(BtreeBucket *node, Item *item, BtreeBucket *child, int *path)
{
    if (node != NULL)
    {
        //assign the value
        node->MakeSpaceInBucket(path[node->layer]+1, 2);
        node->ptrs[path[node->layer]+1] = item;
        node->ptrs[path[node->layer]+2] = child;

        //full or not?
        if (node->element_num < 2*BTREEDEGREE+1)
            return;

        //Like the insertion into leaf bucket,  check if can move some nodes from left neighbor
        if (node->prev_leaf != NULL
            && node->prev_leaf->father == node->father
            && node->prev_leaf->element_num < BTREEDEGREE * 1.6)
        {
            //roll the anchor to current bucket
            void *anchor = node->father->ptrs[path[node->layer+1]-1];
            // BTREEDEGREE*0.1 nodes means BTREEDEGREE*0.2 elements 
            anchor = node->MoveLeftToNodeBucket(BTREEDEGREE*0.1, node->prev_leaf, anchor);
            // the moved nodes' father need to be update
            node->prev_leaf->FixChildFatherLink();
            //the new anchor
            node->father->ptrs[path[node->layer+1]-1] = anchor;
        }
        //Opposite to left
        else if (node->next_leaf != NULL
            && node->next_leaf->father == node->father
            && node->next_leaf->element_num < BTREEDEGREE * 1.6)
        {
            void *anchor = node->father->ptrs[path[node->layer+1]+1];
            anchor = node->MoveRightToNodeBucket(BTREEDEGREE*0.1, node->next_leaf, anchor);
            node->next_leaf->FixChildFatherLink();
            node->father->ptrs[path[node->layer+1]+1] = anchor;
        }
        //split a new node bucket at right side
        else
        {
            BtreeBucket *new_leaf = alloc_bucket();
            if (node->next_leaf != NULL)
                node->next_leaf->prev_leaf = new_leaf;
            new_leaf->next_leaf = node->next_leaf;
            new_leaf->prev_leaf = node;
            node->next_leaf = new_leaf;
            new_leaf->father = node->father;
            new_leaf->layer = node->layer;
            new_leaf->element_num = 0;

            //The actual number of elements to be moved is 2*node_num+1
            node->MoveRightToLeafBucket(BTREEDEGREE|0x1, new_leaf);
            //similar as above
            new_leaf->FixChildFatherLink();
            node->element_num--;
            //after split, the right-most element(must be a key) of this bucket should be the new anchor
            insert_node(node->father, reinterpret_cast<Item*>(node->ptrs[2*BTREEDEGREE - (BTREEDEGREE|0x1)]), new_leaf, path);
        }
    }
    else
    {
        //node == NULL means need a new root.
        BtreeBucket *new_leaf = alloc_bucket();
        new_leaf->layer = child->layer + 1;
        //assign with previous root and the child link to be insert.
        new_leaf->ptrs[0] = root;
        new_leaf->ptrs[1] = item;
        new_leaf->ptrs[2] = child;
        new_leaf->element_num = 3;
        root->father = child->father = new_leaf;
        new_leaf->next_leaf = new_leaf->prev_leaf = new_leaf->father = NULL;
        root = new_leaf;
    }
}


void BtreeIndex::delete_node(BtreeBucket *node, int pos, int count, int *path)
{
    node->DeleteInBucket(pos, count);

    //elements too few? 
    if (node->element_num > BTREEDEGREE * 0.7)
        return;

    //===============================underflow==============================
    //Move nodes from left neighbor if possible
    if (node->prev_leaf != NULL
        && node->prev_leaf->father == node->father 
        && node->prev_leaf->element_num > BTREEDEGREE * 1.3)
    {
        void *anchor = node->father->ptrs[path[node->layer+1]-1];
        anchor = node->prev_leaf->MoveRightToNodeBucket(BTREEDEGREE*0.15, node, anchor);
        node->FixChildFatherLink();
        node->father->ptrs[path[node->layer+1]-1] = anchor;
    }
    //Opposite to above
    else if (node->next_leaf != NULL
        && node->next_leaf->father == node->father
        && node->next_leaf->element_num > BTREEDEGREE * 1.3)
    {
        void *anchor = node->father->ptrs[path[node->layer+1]+1];
        anchor = node->next_leaf->MoveLeftToNodeBucket(BTREEDEGREE*0.15, node, anchor);
        node->FixChildFatherLink();
        node->father->ptrs[path[node->layer+1]+1] = anchor;
    }
    //Merge with right neighbor
    else if (node->next_leaf != NULL
        && node->next_leaf->father == node->father
        && node->next_leaf->element_num + node->element_num < BTREEDEGREE * 1.8)
    {
        BtreeBucket *next_leaf = node->next_leaf;
        node->ptrs[node->element_num] = node->father->ptrs[path[node->layer+1]+1];
        node->element_num++;
        next_leaf->MoveLeftToLeafBucket(next_leaf->element_num, node);
        node->FixChildFatherLink();

        if (next_leaf->next_leaf != NULL)
            next_leaf->next_leaf->prev_leaf = node;
        node->next_leaf = next_leaf->next_leaf;
        free_bucket(next_leaf);

        delete_node(node->father, path[node->layer+1]+1, 2, path);
    }
    //Merge with left neighbor
    else if (node->prev_leaf != NULL
        && node->prev_leaf->father == node->father
        && node->prev_leaf->element_num + node->element_num < BTREEDEGREE * 1.8)
    {
        BtreeBucket *prev_leaf = node->prev_leaf;
        node->MakeSpaceInBucket(0, 1);
        node->ptrs[0] = node->father->ptrs[path[node->layer+1]-1];
        prev_leaf->MoveRightToLeafBucket(prev_leaf->element_num, node);
        node->FixChildFatherLink();
        if (prev_leaf->prev_leaf != NULL)
            prev_leaf->prev_leaf->next_leaf = node;
        node->prev_leaf = prev_leaf->prev_leaf;
        free_bucket(prev_leaf);

        delete_node(node->father, path[node->layer+1]-2, 2, path);
    }
    else if (node->element_num == 1)
    {
        //only one element left, it should be the new root.
        assert(root == node);
        
        BtreeBucket *child = reinterpret_cast<BtreeBucket*>(node->ptrs[0]);
        child->father = NULL;
        root = child;
        free_bucket(node);
    }
    //==============================underflow===============================
}

void BtreeIndex::dfs_destroy(BtreeBucket *node)
{
    if (node->layer == 1)
    {
        for(int i = 0; i < node->element_num; i++) 
            myfree(node->ptrs[i]);
    }
    else
    {
        for(int i = 0; i < node->element_num; i += 2)
        {
            dfs_destroy(reinterpret_cast<BtreeBucket*>(node->ptrs[i]));
            free_bucket(node->ptrs[i]);
        }
    }
    return;
}


BtreeBucket* BtreeIndex::alloc_bucket()
{
    BtreeBucket* res = reinterpret_cast<BtreeBucket*>(mymalloc(sizeof(BtreeBucket)));
    bucket_num++;
    mem_used += sizeof(BtreeBucket);
    return res;  
}

void BtreeIndex::free_bucket(BtreeBucket* bucket)
{
    bucket_num--;
    mem_used -= sizeof(BtreeBucket);
    myfree(bucket);
}


void BtreeBucket::MakeSpaceInBucket(int pos, int count)
{
    assert(element_num + count <= BTREEDEGREE*2+1);
    assert(pos <= element_num);

    for(int i = element_num - 1; i >=pos; --i)
        ptrs[i+count] = ptrs[i];

    element_num += count;
}

void BtreeBucket::DeleteInBucket(int pos, int count)
{
    assert(element_num >= count);
    assert(pos >= 0);

    element_num -= count;
    for(int i = pos; i < element_num; ++i)
        ptrs[i] = ptrs[i+count];
}


void* BtreeBucket::MoveRightToNodeBucket(int count, BtreeBucket *right_neighbour, void *father_anchor)
{
    assert(right_neighbour->father == father);

    //firstly, father_anchor roll down to right bucket.
    right_neighbour->MakeSpaceInBucket(0, count*2);
    right_neighbour->ptrs[count*2-1] = father_anchor;

    //move the key/links to right
    for(int i = 0; i < count*2-1; ++i)
        right_neighbour->ptrs[i] = ptrs[element_num-count*2+1+i];
    //decide the new anchor to be rolled up
    father_anchor = ptrs[element_num-count*2];

    DeleteInBucket(element_num-count*2, count*2);
    return father_anchor;
}


void* BtreeBucket::MoveLeftToNodeBucket(int count, BtreeBucket *left_neighbour, void *father_anchor)
{
    assert(left_neighbour->father == father);

    left_neighbour->ptrs[left_neighbour->element_num] = father_anchor;
    for(int i = 0; i < count*2-1; ++i)
        left_neighbour->ptrs[left_neighbour->element_num + i + 1] = ptrs[i];

    father_anchor = ptrs[count*2-1];
    left_neighbour->element_num += count*2;
    DeleteInBucket(0, count*2);
    return father_anchor;
}

void BtreeBucket::MoveRightToLeafBucket(int count, BtreeBucket *right_neighbour)
{
    assert(right_neighbour->father == father);

    //Just move elements, no anchor operation
    right_neighbour->MakeSpaceInBucket(0, count);
    for(int i = 0; i < count; ++i)
        right_neighbour->ptrs[i] = ptrs[element_num-count+i];

    DeleteInBucket(element_num - count, count);
}

void BtreeBucket::MoveLeftToLeafBucket(int count, BtreeBucket *left_neighbour)
{
    assert(left_neighbour->father == father);

    for(int i = 0; i < count; ++i)
        left_neighbour->ptrs[left_neighbour->element_num  + i] = ptrs[i];

    left_neighbour->element_num += count;
    DeleteInBucket(0, count);
}


void BtreeBucket::FixChildFatherLink()
{
    assert(layer > 1);

    //from left side
    for(int i = 0; i < element_num; i += 2)
    {
        if (reinterpret_cast<BtreeBucket*>(ptrs[i])->father != this)
            reinterpret_cast<BtreeBucket*>(ptrs[i])->father = this;
        else
            break;
    }

    //from right side
    for(int i = element_num - 1; i >= 0; i -= 2)
    {
        if (reinterpret_cast<BtreeBucket*>(ptrs[i])->father != this)
            reinterpret_cast<BtreeBucket*>(ptrs[i])->father = this;
        else
            break;
    }

}


int BtreeBucket::FindPosNode(Item *item, int (*compare_func)(Item *, Item *))
{
    int child_num = element_num >> 1;
    int start = 0, end = child_num - 1, mid;

    if (end < 0) return 0;

    //binary search
    while(start+1 < end)
    {
        mid = (start + end) >> 1;
        int cmp = compare_func(item,reinterpret_cast<Item*>(ptrs[2*mid+1]));
        if (cmp < 0) end = mid;
        else if (cmp > 0) start = mid;
        else return (2*mid+2); // cmp == 0
    }

    for (start = 2*start+1 ; start <= 2*end+1 ; start+=2)
    {
        int res = compare_func(item,reinterpret_cast<Item*>(ptrs[start]));
        if (res == 0) return start+1;
        else if (res < 0) return start-1;
    }
    //the return value always be positive
    return element_num-1;
}


int BtreeBucket::FindPosLeaf(Item *item, int (*compare_func)(Item *, Item *))
{
    int start = 0, end = element_num - 1, mid;
    if (end < 0) return -1;

    while(start+1 < end)
    {
        mid = (start + end) >> 1;
        int cmp = compare_func(item,reinterpret_cast<Item*>(ptrs[mid]));
        if (cmp < 0) end = mid;
        else if (cmp > 0) start = mid;
        else return mid; //cmp == 0
    }

    for (start ; start <= end; start++)
    {
        int res = compare_func(item,reinterpret_cast<Item*>(ptrs[start]));
        if (res == 0) return start;
        else if (res < 0) return -start-1;
    }
    //return positive indicates found at the leaf, otherwise the opposite of where it should be
    return -end-2;
}

